import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;


public class InsertionSorter<T> {
	public boolean PRINTSTEPS = false;
	private String optionalFile;
	private BufferedWriter myWriter = null;
	private Comparable<T>[] myData;
	private  Comparable<T>[] sortedData;
	
	public InsertionSorter(Comparable<T>[] data){
		myData = data;
		sortedData = new Comparable[myData.length];
	}
	
	public InsertionSorter(Comparable<T>[] data, String outputFile){
		myData = data;
		sortedData = new Comparable[myData.length];
		PRINTSTEPS = true;
		optionalFile = outputFile;
	}
	
	public Comparable<T>[] sort(){
		/*
		 * Open file if PRINTSTEPS has been requested
		 */
		if(PRINTSTEPS){
			try {
				myWriter = new BufferedWriter(new FileWriter(optionalFile));
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		
		for(int i = 0; i < myData.length; i++){
			insert(myData[i],i);
			if(PRINTSTEPS){				
				try {
					myWriter.write(ArrayGetter.getPrintedContents(sortedData));
					myWriter.newLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
		
		/*
		 * Close file if PRINTSTEPS has been requested
		 */
		if(PRINTSTEPS){
			try {
				myWriter.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return sortedData;
	}
	
	private void insert(Comparable<T> item, int currNum){
		if(currNum==0){
			sortedData[currNum] = item;
		}else{
			int pos = linearSearch(item,sortedData);
			for(int i=currNum,prev=i;i>=pos;i--){
				sortedData[prev] = sortedData[i];
				prev = i;
			}
			sortedData[pos] = item;
		}
	}
	
	public static int linearSearch(Comparable item, Comparable[] data){
		for(int i=0;i<data.length;i++){
			if(data[i]!=null){
				if(item.compareTo(data[i])<0){
					return i;
				}
			}else{
				return i;
			}
		}
		return 0;
	}
	
	public static int binarySearch(int low, int high, Comparable item, Comparable[] data){
		int mid = (int)Math.floor(low+(high-low)/2);
		if(low==high){
			return mid;
		}
		int result = item.compareTo(data[mid]);		

		if(high<low){
			return high;
		}else if(result==0){
			return mid;
		}else if(result>0){
			return binarySearch(mid+1,high,item,data);
		}else{
			return binarySearch(low,mid-1,item,data);
		}		
	}
}
